#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        if (len < 2)return s;
        int maxlen = 0;
        int star = 0;

        vector<vector<bool>> dp(len, vector<bool>(len, false));

        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        for (int l = 1; l <= len; l++)
        {
            for (int i = 0; i + l - 1 < len; i++) {
                int j = i + l - 1;
                if (s[i] != s[j]) {
                    dp[i][j] = false;
                }
                else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    }
                    else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                if (dp[i][j] && l > maxlen) {
                    maxlen = l;
                    star = i;
                }
            }
        }
        return s.substr(star, maxlen);
    }
};